/**
 * 300. 最长递增子序列
 * https://leetcode.cn/problems/longest-increasing-subsequence/description/
 */
//动态规划
class Solution {
    public int lengthOfLIS(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];
        int ret = 0;
        Arrays.fill(dp, 1);
        //填表顺序 后->前
        for(int i = n - 1; i >= 0; i--) {
            for(int j = i + 1; j < n; j++) {
                if(nums[j] > nums[i]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            ret = Math.max(ret, dp[i]);
        }
        return ret;
    }
}

// //记忆化搜索
// class Solution2 {
//     int[] mermoy;
//     public int lengthOfLIS(int[] nums) {
//         int ret = 0;
//         int n = nums.length;
//         mermoy = new int[n];
//         for(int i = 0; i < n; i++) {
//             ret = Math.max(ret, dfs(i, nums));
//         }
//         return ret;
//     }

//     public int dfs(int pos, int[] nums) {
//         int ret = 1;
//         if(mermoy[pos] != 0) {
//             return mermoy[pos];
//         }
//         for(int i = pos + 1; i < nums.length; i++) {
//             if(nums[i] > nums[pos] && mermoy[pos] == 0) {
//                 ret = Math.max(ret, dfs(i, nums) + 1);
//             }
//         }
//         mermoy[pos] = ret;
//         return ret;
//     }
// }

// //递归，超时
// class Solution3 {
//     public int lengthOfLIS(int[] nums) {
//         int ret = 0;
//         int n = nums.length;
//         for(int i = 0; i < n; i++) {
//             ret = Math.max(ret, dfs(i, nums));
//         }
//         return ret;
//     }

//     public int dfs(int pos, int[] nums) {
//         int ret = 1;
//         for(int i = pos + 1; i < nums.length; i++) {
//             if(nums[i] > nums[pos]) {
//                 ret = Math.max(ret, dfs(i, nums) + 1);
//             }
//         }
//         return ret;
//     }
// }